/*
https://leetcode.cn/problems/kth-missing-positive-number/description/
1539. 第k个缺失的正整数
medium, 方钊堉 2024.09.17
二分查找
*/

class Solution {
public:
    int findKthPositive(vector<int>& arree, int ke) {
        // 特殊情况处理：如果数组的第一个元素大于 ke，则 ke 本身就是答案。
        if (arree[0] > ke) {
            return ke;
        }

        int left = 0, r = arree.size();
        // 二分查找循环，直到左右边界重合。
        while (left < r) {
            int e = (left + r) >> 1;
            int x = e < arree.size() ? arree[e] : INT_MAX;
            if (x - e - 1 >= ke) {
                r = e;
            } else {
                left = e + 1;
            }
        }
            // 计算第 k 个缺失的正整数。
        // 如果 left 位置的前一个位置的值减去索引再减去 1 的结果小于 k，
        // 则需要加上 k 与前面计算出的差值的差额。
        return ke - (arree[left - 1] - (left - 1) - 1) + arree[left - 1];
    }
};
